package com.markus.code.二叉树.study;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/30 20:23
 * todo: 二叉树的深度
 */
public class DepthTree {
    /**
     * 都知道，二叉树的深度用递归非常好做，现在来做下非递归的方法
     * 非递归的方法就是用bfs的算法
     */
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public int maxDepth(TreeNode root){
        if (root == null){
            return 0;
        }
        int depth = 0;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        while(!deque.isEmpty()){
            int size = deque.size();
            for (int i=0;i<size;i++){
                TreeNode node = deque.pollFirst();
                if (node.left != null){
                    deque.addLast(node.left);
                }
                if (node.right != null){
                    deque.addLast(node.right);
                }
            }
            depth++;
        }
        return depth;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        DepthTree demo = new DepthTree();
        System.out.println(demo.maxDepth(root));
    }
}
